package com.yc.leetcode;

import java.util.Stack;

public class D20230407 {

    public static void main(String[] args) {
        D20230407 d = new D20230407();
//        System.out.println(d.multiplyStrings("12","12"));
//        System.out.println(d.isValid("([{}]{})"));
        System.out.println(d.isValid2("([{{}])"));
    }

    /**
     * 输入两个字符串(小于110位)，字符串内容都是正整数。返回这两个数字字符串的乘积的字符串。
     * 不可直接转成BigDecimal计算
     *
     * 思路：竖式乘法的方法来计算两个正整数的乘积
     * @param num1
     * @param num2
     * @return
     */
    public static String multiplyStrings(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];//难点1: 知道两个数相乘的最大长度 难点2：理解竖乘的本质

        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';//巧妙方法：字符直接转int。 连转换为int数组都不再需要
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                int product = x * y;
                int p1 = i + j, p2 = i + j + 1;
                int sum = product + pos[p2];

                pos[p1] += sum / 10;
                pos[p2] = sum % 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int p : pos) if (sb.length() != 0 || p != 0) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }

    /**
     * 用java写一段算法,要求如下：
     * 输入一个字符串，字符串由'(',')','{','}','[',']'构成，
     * 判断字符串是否符合正常的"有头有尾"写法。符合返回true，否则返回false
     *
     * 用栈（jvm的算法）
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                        (c == ']' && top != '[') ||
                        (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    static int index = 0;
    /**
     * 递归算法。。。不好弄：难点：是继续循环还是返回不好判断，而且后面的括号要找到前面对应的括号，不好找
     * @param s
     * @return
     */
    @Deprecated
    public static boolean isValid2(String s) {
        for (int i = index+1; i < s.length(); i++) {
            char p = s.charAt(index);
            char e = s.charAt(i);
            if (e == '(' || e == '[' || e == '{') {//左括号---》更新index，递归
                index = i;
                return isValid2(s);//子序列符合 ---》 继续  不符合 返回
            } else if ((p == '(' && e == ')') ||
                    (p == '[' && e == ']') ||
                    (p == '{' && e == '}')) {//符合 --》 从下一个字符开始
                index = i + 1;
                i = index;//index发生"突变"，i也跟着突变(循环回去的时候会自动+1)
                //如果下一个是右括号：返回。 下一个是左括号：继续
                p = s.charAt(index);
                if (p == ')' || p == ']' || p == '}') {
                    return true;
                }
            } else {//不符合   结束
                return false;
            }
        }
        return true;
    }


}
